package divide;

/**
 * 最大子数组和问题
 */
public class MaxSubArraySum {

    public static void main(String[] args) {
        int[] nums = { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 };

        ArraySum arraySum = findMaxSubArraySum(nums, 0, nums.length - 1);

        System.out.println("拥有最大和的子数组下标为：" + arraySum.left + "--" + arraySum.right);
        System.out.println("数组中，拥有最大和的子数组为：");
        for (int i = arraySum.left; i <= arraySum.right; i++) {
            System.out.print(nums[i] + ",");
        }
        System.out.println("最大的子数组和为：" + arraySum.sum);
    }

    private static ArraySum findMaxSubArraySum(int[] nums, int left, int right) {
        if (left == right) {
            ArraySum arraySum = new ArraySum();
            arraySum.setLeft(left);
            arraySum.setRight(right);

            arraySum.setSum(nums[left]);
            return arraySum;
        }

        int middleIndex = (left + right) / 2;
        ArraySum leftSum = findMaxSubArraySum(nums, left, middleIndex);
        ArraySum rightSum = findMaxSubArraySum(nums, middleIndex + 1, right);
        ArraySum crossSum = findCrossMaxSubArraySum(nums, left, middleIndex, right);
        if (leftSum.sum >= rightSum.sum && leftSum.sum >= crossSum.sum) {
            return leftSum;
        }
        if (rightSum.sum >= leftSum.sum && rightSum.sum >= crossSum.sum) {
            return rightSum;
        }
        return crossSum;
    }

    private static ArraySum findCrossMaxSubArraySum(int[] nums, int left, int middle, int right) {
        int leftSum = -1000;
        int leftIndex = middle;
        int sum = 0;
        for (int i = middle; i >= left; i--) {
            sum = sum + nums[i];
            if (sum > leftSum) {
                leftSum = sum;
                leftIndex = i;
            }
        }

        int rightSum = -1000;
        int rightIndex = middle + 1;
        sum = 0;
        for (int i = middle + 1; i < right; i++) {
            sum = sum + nums[i];
            if (sum > rightSum) {
                rightSum = sum;
                rightIndex = i;
            }
        }
        ArraySum arraySum = new ArraySum();
        arraySum.setSum(leftSum + rightSum);
        arraySum.setLeft(leftIndex);
        arraySum.setRight(rightIndex);
        return arraySum;
    }

    private static class ArraySum {
        private int sum;

        private int left;

        private int right;

        public int getSum() {
            return sum;
        }

        public void setSum(int sum) {
            this.sum = sum;
        }

        public int getLeft() {
            return left;
        }

        public void setLeft(int left) {
            this.left = left;
        }

        public int getRight() {
            return right;
        }

        public void setRight(int right) {
            this.right = right;
        }
    }

}
